package com.shm.leetcode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author: shm
 * @dateTime: 2020/9/22 10:25
 * @description: 面试题 16.26. 计算器
 * 给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。
 *
 * 表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格  。 整数除法仅保留整数部分。
 *
 * 示例 1:
 *
 * 输入: "3+2*2"
 * 输出: 7
 * 示例 2:
 *
 * 输入: " 3/2 "
 * 输出: 1
 * 示例 3:
 *
 * 输入: " 3+5 / 2 "
 * 输出: 5
 * 说明：
 *
 * 你可以假设所给定的表达式都是有效的。
 * 请不要使用内置的库函数 eval。
 */
public class Calculator {
    public int calculate(String s) {
        char[] chars = s.trim().toCharArray();
        Deque<Integer> deque = new LinkedList<>();
        int res=0,i=0;
        while (i<chars.length){
            if (chars[i]==' '){
                i++;
                continue;
            }
            char temp = chars[i];
            if (temp=='+'||temp=='*'||temp=='/'||temp=='-'){
                i++;
                while (i<chars.length&&chars[i]==' '){
                    i++;
                }
            }
            int num = 0;
            //Character.isDigit() 方法用于判断指定字符是否为数字。
            while (i<chars.length&&Character.isDigit(chars[i])){
                num = num*10+chars[i]-'0';
                i++;
            }
            switch (temp){
                case '-':
                    num=-num;
                    break;
                case '*':
                    num=deque.pop()*num;
                    break;
                case '/':
                    num=deque.pop()/num;
                    break;
                default:
                    break;
            }
            deque.push(num);
        }
        while (!deque.isEmpty()){
            res+=deque.pop();
        }
        return res;
    }

    public int calculate_2(String s) {
        Stack<Integer> ss = new Stack<>();
        int d=0;
        char sign = '+';
        int ans = 0;
        char[] cc = s.toCharArray();
        int n = cc.length;
        for(int i=0;i<n;i++){
            if(Character.isDigit(cc[i])){
                d = d*10+(int)(cc[i]-'0');
            }
            if(!Character.isDigit(cc[i])&&cc[i]!=' ' || i==n-1){
                switch(sign){
                    case '+':
                        ss.push(d);
                        break;
                    case '-':
                        ss.push(-d);
                        break;
                    case '*':
                        ss.push(ss.pop()*d);
                        break;
                    case '/':
                        ss.push(ss.pop()/d);
                        break;
                    default:
                        break;
                }
                sign = cc[i];
                d=0;
            }
        }
        while(!ss.isEmpty()){
            ans+=ss.pop();
        }
        return ans;
    }
}
